package com.bilibili.interview;

import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe: 某次漫展, 已知有 n 个打卡点 , 每个员工打卡点需要 m_i 分钟完成, 完成后获得奖励 r_i , 已打卡过的点不能再去 , 需要在规定的 m 分钟内完成 , 尽可能多的获得奖励 .
 * 典型的 0-1 背包问题 , 题意转化: n 个物品 , 背包体积 m , 每个物品 体积 m_i , 价值 r_i , 且每个物品不能重复取
 * @date 2021/07/09
 */

public class One_01Package {

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int V = input.nextInt();
        int[] weight = new int[N];
        int[] values = new int[N];
        for(int i = 0 ; i < N ; i ++){
            int wei = input.nextInt();
            int val = input.nextInt();
            weight[i] = wei;
            values[i] = val;
        }

        // 0 - 1 背包核心
        int[] dp = new int[V + 1];
        for(int i = 0 ; i < N ; i ++){ // 遍历物品
            for(int j = V ; j >= weight[i] ; j --){ // 遍历背包
                dp[j] = Math.max(dp[j] , dp[j - weight[i]] + values[i]);
            }
        }
        System.out.println(dp[V]);
    }
}
